package impl;

import anaydis.sort.SorterType;
import org.jetbrains.annotations.NotNull;

import java.util.Comparator;
import java.util.List;

public class QuickSortThreeWayPartition extends AbstractQuickSorter {

    public QuickSortThreeWayPartition() {
        super(SorterType.QUICK_THREE_PARTITION);
    }

    public <T> void sort(@NotNull Comparator<T> comparator,@NotNull List<T> list) {
        sort(comparator, list, 0, list.size() - 1);
    }

    private <T> void sort(Comparator<T> comparator, List<T> list, int left, int right) {
        if (right <= left) return;
        int i = left - 1;
        int j = right;
        int p = left - 1;
        int q = right;
        int k;
        for (; ;) {
            while (greater(comparator,list, right, ++i)) ;
            while (greater(comparator,list, --j, right)) if (j == left) break;
            if (i >= j) break;
            swap(list, i, j);
            if (this.equals(comparator,list, i, right)) {
                p++;
                swap(list, p, i);
            }
            if (equals(comparator, list, right, j)) {
                q--;
                swap(list, q, j);
            }
        }
        swap(list, i, right);
        j = i - 1;
        i = i + 1;
        for (k = left; k <= p; k++, j--)
            swap(list, k, j);
        for (k = right - 1; k >= q; k--, i++)
            swap(list, k, i);
        sort(comparator, list, left, j);
        sort(comparator, list, i, right);
    }
}
